#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO
{
	template<typename T>
	void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
	template<typename T,typename... Args>
	void read(T &_x,Args&...others){Read(_x);Read(others...);}
	const int BUF=20000000;char buf[BUF],to,stk[32];int plen;
	#define pc(x) buf[plen++]=x
	#define flush(); fwrite(buf,1,plen,stdout),plen=0;
	template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 100,mod = 111121;
int n,a[N],x,y,head[N],fa[N][20],lg[N],dep[N],dep1[N],dep2[N],cnt,ans,o,o1;
struct w
{
	int to,nxt;
}c[N<<1];
inline void add(int x,int y)
{
	c[++cnt].nxt = head[x];
	c[cnt].to = y;
	head[x] = cnt;
}
void dfs(int x,int y)
{
	dep[x] = dep[y]+1; fa[x][0] = y;
	for(int i = 1;i <= 10;i++) fa[x][i] = fa[fa[x][i-1]][i-1];
	for(int i = head[x];i;i = c[i].nxt)
		if(c[i].to != y) dfs(c[i].to,x),fa[x][0] = y;
}
int lca(int x,int y)
{
	if(dep[x] < dep[y]) swap(x,y);
	while(dep[x] != dep[y]) x = fa[x][lg[dep[x]-dep[y]]];
	if(x == y) return x;
	for(int i = 10;i >= 0;i--)
		if(fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
	return fa[x][0];
}
void dfs1(int x,int y)
{
	if(x == y) return;
	if(o == -1) o = a[x];
	else o = (o&a[x]);
	dfs1(fa[x][0],y);
} 
void dfs2(int x,int y)
{
	if(x == y) return;
	if(o1 == -1) o1 = a[x];
	else o1 = (o1|a[x]);
	dfs2(fa[x][0],y);
} 
inline ksm(int x,int p)
{
	int ans = 1;
	if(x == 0) return 0;
	while(p)
	{
		if(p%2==1) ans = ans*x%mod;
		x = x*x%mod;
		p>>=1;
	}
	return ans;
}
signed main()
{
	freopen("abstract.in","r",stdin);
	freopen("abstract.out","w",stdout);
	read(n);
	for(int i = 1;i <= n;i++) read(a[i]);
	for(int i = 2;i <= n;i++) lg[i] = lg[i/2]+1;
	for(int i = 1;i < n;i++) read(x),read(y),add(x,y),add(y,x);
	dfs(1,0);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= i;j++)
		{
			o = o1 = -1;
			dfs1(i,lca(i,j)); dfs1(j,lca(i,j)); 
			if(lca(i,j) != 0 && o == -1) o = a[lca(i,j)];
			else if(lca(i,j) != 0) o = (o&a[lca(i,j)]);
			dfs2(i,lca(i,j)); dfs2(j,lca(i,j));
			if(lca(i,j) != 0 && o1 == -1) o1 = a[lca(i,j)];
			else if(lca(i,j) != 0) o1 = (o1|a[lca(i,j)]);
			ans = (ans+ksm(o,o1))%mod;
		}
	print(ans); flush();
	return 0;
}



